package algorithm.backtracing;

import util.GsonUtil;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 37. Sudoku Solver
 * leetcode : https://leetcode.com/problems/sudoku-solver/
 * Difficulty : Hard
 *
 * 求解数独
 */
public class SudokuSolver {

    public static void main(String[] args) {
        char[][] sudoku = new char[9][9];
        sudoku[0] = new char[]{'.','.','.','6','.','.','.','3','5'};
        sudoku[1] = new char[]{'5','.','.','.','.','.','6','.','.'};
        sudoku[2] = new char[]{'3','9','6','.','.','5','.','.','.'};
        sudoku[3] = new char[]{'9','2','4','5','1','7','3','8','6'};
        sudoku[4] = new char[]{'6','5','.','4','8','3','.','.','.'};
        sudoku[5] = new char[]{'8','.','3','2','9','6','5','.','4'};
        sudoku[6] = new char[]{'.','6','8','7','5','.','.','4','3'};
        sudoku[7] = new char[]{'.','.','5','.','.','.','.','6','8'};
        sudoku[8] = new char[]{'4','3','9','1','6','8','.','5','.'};

        long begin = System.currentTimeMillis();
        solveSudoku_fast(sudoku);
//        solveSudoku_optimize(sudoku);
        long end = System.currentTimeMillis();
        System.out.println(String.format("耗时:%s毫秒",(end-begin)));
        Arrays.stream(sudoku).forEach(line -> System.out.println(GsonUtil.toJson(line)));
//        System.out.println(GsonUtil.toJson(sudoku));
    }


    /**
     * Leetcode上看到的解法,非常非常快，执行只需要2ms
     * 思路：
     * rows 和 cols 还有boxs。把矩阵中的数字，变换为是否占位。
     *      比如 rows[0][1] = true；表示第0行里面，已经有1这个数字了。
     * 那么：
     * 第一行{5,3,7}就可以变为 rows[0] = {false,false,true,false,true,false,true,false,false};
     * 第一个格子{3,5,6,8,9}就变为 boxes[0] = {false,false,true,false,true,true,false,true,true};
     *
     * 利用了动态规划的思路，把已经计算过的结果存储到rows cols boxes 中。
     * 并且校验是否可以填入该空位的思路很巧妙，只需要取 rows cols boxes 该数字转为坐标的boolean值，只要有一个为true那就说明有重复数字，不能填入。
     *
     * @param board
     */
    public static void solveSudoku_fast(char[][] board){
        int n = board.length, cnt = 0;
        boolean[][] rows = new boolean[n][n];
        boolean[][] cols = new boolean[n][n];
        boolean[][] boxes = new boolean[n][n];
        List<int[]> empty = new ArrayList();        // 记录空位的坐标

        // 遍历矩阵，标记空位和非空位
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]!='.'){
                    int index = board[i][j]-'1';    // 找到坐标，因为数组下标从0开始，因此第i个的下标是i-1
                    rows[i][index] = true;
                    cols[j][index] = true;
                    boxes[i/3*3+j/3][index] = true;
                }else{
                    empty.add(new int[]{i, j});
                }
            }
        }
        for(int k=1;k<10;k++){
            if(valid(rows, cols, boxes, board, empty,0, k)){
                return;
            }
        }
    }

    /**
     *
     * @param rows
     * @param cols
     * @param boxes
     * @param board
     * @param empty
     * @param index  empty集合的下标。表示现在填第index个空格
     * @param num
     * @return
     */
    public static boolean valid(boolean[][] rows, boolean[][] cols, boolean[][] boxes, char[][] board,
                         List<int[]> empty, int index,int num){
        if(index==empty.size()){
            return true;
        }

        int i = empty.get(index)[0];
        int j = empty.get(index)[1];

        // 通过验证 rows cols boxes 三个位置的boolean值，来验证 num是否可以填入[i,j] 这个位置
        if(rows[i][num-1] || cols[j][num-1] || boxes[i/3*3+j/3][num-1]){
            return false;
        }

        rows[i][num-1] = true;
        cols[j][num-1] = true;
        boxes[i/3*3+j/3][num-1] = true;
        board[i][j] = (char)(num+'0');
        for(int k=1;k<10;k++){
            if(valid(rows, cols, boxes, board, empty, index+1, k)) {
                return true;
            }
        }

        // 回溯，把该次修改的值都改回去
        rows[i][num-1] = false;
        cols[j][num-1] = false;
        boxes[i/3*3+j/3][num-1] = false;
        board[i][j] = '.';
        return false;
    }


    /**
     * 执行时间6ms
     * 参考fast算法，用自己的回溯思路完成
     * @param board
     */
    public static void solveSudoku_optimize(char[][] board){
        List<List<Integer>> emptyList = new ArrayList<>();
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j] == '.'){
                    emptyList.add(Arrays.asList(new Integer[]{i,j}));
                }
            }
        }

        for(int val=1; val<=9; val++){
            if(solve_optimize(board, emptyList, 0, val)){
                return;
            }
        }

    }

    public static boolean solve_optimize(char[][] board, List<List<Integer>> emptyList, int index, int val){
        if(index == emptyList.size()){
            return true;
        }
        int i = emptyList.get(index).get(0);
        int j = emptyList.get(index).get(1);
        if(checkValid(board, val, i, j)){
            board[i][j] = (char) (val + '0');
            for(int tmp=1; tmp<=9; tmp++){
                if(solve_optimize(board, emptyList, index+1, tmp)){
                    return true;
                }
            }
            board[i][j] = '.';
        }

        return false;
    }

    public static boolean checkValid(char[][] board, int val, int x, int y){
        for(int t = 0; t<9; t++){
            // check rows and cols
            if(board[x][t] != '.' && board[x][t] == val+'0') return false;
            if(board[t][y] != '.' && board[t][y] == val+'0') return false;
            // check blocks
            int tx = (x/3)*3 + t/3;
            int ty = (y/3)*3 + t%3;
            if(board[tx][ty] != '.' && board[tx][ty] == val+'0') return false;
        }

        return true;
    }
}
